package _7

//[
//	[1,1,0],
//	[1,1,0],
//	[0,0,1]
//]
// 试着使用深度优先搜索和深度优先搜索以及并查集的方案去解决他
func findCircleNum(isConnected [][]int) int {
	return v2(isConnected)
}

func v2(isConnected [][]int) int {
	// cnt 表示连通分量
	cnt := 0
	// visited 表示已经访问的顶点
	visited := make(map[int]bool)

	q := make([]int, 0)
	for i := 0; i < len(isConnected); i++ {
		if !visited[i] {
			cnt++
			q = append(q, i)
			for len(q) > 0 {
				curi := q[0]
				q = q[1:]
				visited[curi] = true
				for j := range isConnected[curi] {
					if curi != j && !visited[j] && isConnected[curi][j] == 1 {
						q = append(q, j)
					}
				}
			}
		}
	}
	return cnt
}

func v1(isConnected [][]int) int {
	// n 表示顶点数量
	n := len(isConnected)

	// cnt 表示连通分量
	cnt := 0

	// visited 表示已经访问的顶点
	visited := make(map[int]bool)

	for i := 0; i < n; i++ {
		if !visited[i] {
			cnt += 1
			dfs(isConnected, i, visited)
		}
	}

	return cnt
}

func dfs(graph [][]int, startPoint int, visited map[int]bool) {
	visited[startPoint] = true
	for i := 0; i < len(graph); i++ {
		if i != startPoint && graph[startPoint][i] == 1 {
			if !visited[i] {
				dfs(graph, i, visited)
			}
		}
	}
}
